package com.liang.leetcode.array;

/**
 * 05：螺旋矩阵Ⅱ
 * 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
 * 示例：
 * 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
 */
public class Array05_GenerateMatrix {
    public static void main(String[] args) {
        int n = 3;
        int[][] matrix = generateMatrix2(n);
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                // System.out.print(matrix[i][j]+" ");
                System.out.print(String.format("%0" + 2 + "d ", matrix[i][j])); // 左侧补0输出
            }
            System.out.println();
        }
    }

    /**
     * 生成一个顺时针螺旋排列的正方形矩阵
     * @param n 矩阵的边长
     * @return 生成的正方形矩阵
     */
    public static int[][] generateMatrix(int n) {
        int loop = 0; // 记录当前遍历到的层数
        int[][] res = new int[n][n];  // 创建结果矩阵
        int start = 0; // 记录每一层起始位置
        int count = 1; // 定义填充的数字
        int i, j; // 矩阵中的行和列

        // 从外向内逐层填充
        while (loop++ < n / 2) {
            //上侧从左到右，i不动,j++
            for (j = start; j < n - loop; j++) {
                res[start][j] = count++;
            }
            //右侧从上到下，i++,j不动
            for (i = start; i < n - loop; i++) {
                res[i][j] = count++;
            }
            //下侧从右到左，i不动，j--
            for (; j >= loop; j--) {
                res[i][j] = count++;
            }
            //左侧从下到上，i--,j不动
            for (; i >= loop; i--) {
                res[i][j] = count++;
            }
            start++; //遍历下一层
        }
        // 若矩阵边长为奇数，则填充中心位置
        if (n % 2 == 1) {
            res[start][start] = count;
        }
        return res;
    }

    /**
     * for循环中变量定义成i或j的细节：按照通常的思维，i代表行，j代表列
     * 这样，就可以很容易区分出来变化的量应该放在[][]的第一个还是第二个
     * 对于变量的边界怎么定义：
     * 从左向右填充：填充的列肯定在[left,right]区间
     * 从上向下填充：填充的行肯定在[top,bottom]区间
     * 从右向左填充：填充的列肯定在[right,left]区间
     * 从下向上填充：填充的行肯定在[bootom,top]区间
     * 通过上面的总结会发现边界的起始和结束与方向是对应的
     */
    public static int[][] generateMatrix2(int n) {
        int left = 0, right = n - 1, top = 0, bottom = n - 1;
        int count = 1, target = n * n;
        int[][] res = new int[n][n];

        while (count <= target) {
            //从左到右填充，相当于缩小上边界
            for (int j = left; j <= right; j++)
                res[top][j] = count++;
            top++; //缩小上边界
            //从上向下填充，相当于缩小右边界
            for (int i = top; i <= bottom; i++)
                res[i][right] = count++;
            right--; //缩小右边界
            //从右向左填充，相当于缩小下边界
            for (int j = right; j >= left; j--)
                res[bottom][j] = count++;
            bottom--; //缩小下边界
            //从下向上填充，相当于缩小左边界
            for (int i = bottom; i >= top; i--)
                res[i][left] = count++;
            left++; //缩小左边界
        }
        return res;
    }


}
